package leetcode.editor.cn;


import fileDemo.mfile.FileUtils;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

//[912]排序数组
public class SortAnArray912 {
    public static void main(String[] args) {
        Solution solution = new SortAnArray912().new Solution();
        String s = FileUtils.readFile2String("./src/leetcode/editor/cn/SortAnArray912_TestData.txt");
        try {
            String[] numbers = s.split(",");
            List<Integer> dataList = new ArrayList<>();
            for (String number : numbers) {
                dataList.add(Integer.parseInt(number.trim())); // 转换为整数并添加到列表
            }
            int[] numData = dataList.stream().mapToInt(i -> i).toArray();

            long start = System.currentTimeMillis();
            int[] ints = solution.sortArray(numData);
            System.out.println("SortAnArray912:main:end time:" + (System.currentTimeMillis() - start));

            System.out.println("SortAnArray912:main:" + isSorted(ints));
        } catch (Exception e) {
            e.printStackTrace();
        }

    }

    /**
     * 检查数组是否有序（非递减顺序）
     *
     * @param array 待检查的数组
     * @return 如果数组有序则返回 true，否则返回 false
     */
    public static boolean isSorted(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            if (array[i] > array[i + 1]) {
                return false; // 如果前一个元素大于后一个元素，说明数组无序
            }
        }
        return true; // 所有元素都按顺序排列，数组有序
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[] sortArray(int[] nums) {
            if (nums == null || nums.length < 1) return nums;
//            mQuicksort(nums, 0, nums.length - 1);
            mergeSort(nums, 0, nums.length - 1);
//            heapSort(nums);

            return nums;
        }

        //堆排序  	执行耗时:87 ms,击败了39.59% 的Java用户 //	内存消耗:55.4 MB,击败了47.19% 的Java用户
        private void heapSort(int[] nums) {
            PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(nums.length);
            for (int i = 0; i < nums.length; i++) {
                priorityQueue.offer(nums[i]);
            }
            for (int i = 0; i < nums.length; i++) {
                nums[i] = priorityQueue.poll();
            }
        }

//        为什么
//        mergeSort(nums, left, mid);
//        mergeSort(nums, mid + 1, right);
//
//        这 2 行修改为 下面的这 2 行就不能运行了呢？
//            mergeSort(nums, left, mid-1);
//            mergeSort(nums, mid, right);
        /**
         * 原始方法：mergeSort(nums, left, mid)和mergeSort(nums, mid + 1, right)无重叠，正确分割数组。
         * 修改方法：mergeSort(nums, left, mid-1)和mergeSort(nums, mid, right)导致nums[mid]被重复处理。 举个例子说明
         *
         * ChatGPT
         * 1- 举例说明原始方法和修改方法的差异：
         *
         * 假设我们有一个数组 nums 如下：
         * int[] nums = {4, 3, 2, 1};
         * 我们要对这个数组进行归并排序。
         *
         * 2- 应用原始方法：
         * 第一次递归调用：mergeSort(nums, 0, 3)，mid 计算为 (3 - 0) / 2 + 0 = 1。
         * 分为两部分：mergeSort(nums, 0, 1) 和 mergeSort(nums, 2, 3)。
         * 在第一部分中：
         * 再次分割：mergeSort(nums, 0, 0) 和 mergeSort(nums, 1, 1)，此时每部分只有一个元素。
         * 在第二部分中：
         * 再次分割：mergeSort(nums, 2, 2) 和 mergeSort(nums, 3, 3)，同样，每部分只有一个元素。
         * 然后合并：首先合并单个元素，再合并结果。
         *
         * 3- 应用修改方法：
         *
         * 第一次递归调用：mergeSort(nums, 0, 3)，计算 mid 为 1。
         * 分为两部分：mergeSort(nums, 0, 0) 和 mergeSort(nums, 1, 3)。
         * 在第一部分中：
         * 只有 nums[0]，不需要进一步递归。
         * 在第二部分中：
         * 再次调用：mergeSort(nums, 1, 3)，mid 计算为 (3 - 1) / 2 + 1 = 2。
         * 分为两部分：mergeSort(nums, 1, 1) 和 mergeSort(nums, 2, 3)。
         */


        //归并排序，更稳定。。。不会易出现 快排的worst情况。但是需要单独开辟空间。 	执行耗时:30 ms,击败了64.66% 的Java用户 //	内存消耗:55.7 MB,击败了42.18% 的Java用户
        private void mergeSort(int[] nums, int left, int right) {
            if (left >= right) return;
            int mid = (right - left) / 2 + left;
            mergeSort(nums, left, mid);
            mergeSort(nums, mid + 1, right);
            merge(nums, left, mid, right);
        }
        private void merge(int[] nums, int left, int mid, int right) {
            int[] temp = new int[right - left + 1];
            int lStart = left,rStart = mid + 1, k = 0;//temp fill index.

            while (lStart <= mid && rStart <= right) {
                temp[k++] = nums[lStart] > nums[rStart] ? nums[rStart++] : nums[lStart++];
            }
            while (lStart<=mid){ temp[k++] = nums[lStart++];}
            while (rStart<=right){ temp[k++] = nums[rStart++];}

            for (int i = 0; i < temp.length; i++) {
                nums[left+i] = temp[i];
            }
        }

        //快排 QuickSort	执行耗时:1672 ms,击败了13.84% 的Java用户 //	内存消耗:59.9 MB,击败了11.52% 的Java用户
        private void mQuicksort(int[] nums, int startIndex, int endIndex) {
            if (startIndex >= endIndex) return;
            int pivot = getPartion(nums, startIndex, endIndex);
            mQuicksort(nums, startIndex, pivot - 1);
            mQuicksort(nums, pivot + 1, endIndex);
        }
        private int getPartion(int[] nums, int startIndex, int endIndex) {
            int count = startIndex;
            //不使用最有一个数，做 pivot 了，取中间的数。
            int pivotIndex = (endIndex - startIndex) / 2 + startIndex;
            mSwap(nums, pivotIndex, endIndex);//交换中间---最后。

            int pivotVal = nums[endIndex];
            //i < endIndex 因为  pivot 是最后一个，
            // if pivot is start . i init = startIndex +1
            for (int i = startIndex; i < endIndex; i++) {//pivot的位置不动
                if (nums[i] < pivotVal) {
                    mSwap(nums, i, count);
                    count++;
                }
            }
            //pivot的位置交换到 ，他所在的位置。 [count]>=pivotVal
            mSwap(nums, count, endIndex);
            return count;
        }
        private void mSwap(int[] nums, int i, int j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }

//        private void mergeSort(int)
    }
//leetcode submit region end(Prohibit modification and deletion)

}